<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<title>Presenting Boost.Intrusive containers</title>
<link rel="stylesheet" href="../../../doc/src/boostbook.css" type="text/css">
<meta name="generator" content="DocBook XSL Stylesheets V1.79.1">
<link rel="home" href="../index.html" title="The Boost C++ Libraries BoostBook Documentation Subset">
<link rel="up" href="../intrusive.html" title="Chapter 16. Boost.Intrusive">
<link rel="prev" href="concepts_summary.html" title="Concept summary">
<link rel="next" href="safe_hook.html" title="Safe hooks">
<meta name="viewport" content="width=device-width, initial-scale=1">
</head>
<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF">
<table cellpadding="2" width="100%"><tr>
<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../boost.png"></td>
<td align="center"><a href="../../../index.html">Home</a></td>
<td align="center"><a href="../../../libs/libraries.htm">Libraries</a></td>
<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td>
<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td>
<td align="center"><a href="../../../more/index.htm">More</a></td>
</tr></table>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="concepts_summary.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
<div class="section">
<div class="titlepage"><div><div><h2 class="title" style="clear: both">
<a name="intrusive.presenting_containers"></a><a class="link" href="presenting_containers.html" title="Presenting Boost.Intrusive containers">Presenting Boost.Intrusive
    containers</a>
</h2></div></div></div>
<p>
      <span class="bold"><strong>Boost.Intrusive</strong></span> offers a wide range of intrusive
      containers:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          <span class="bold"><strong>slist</strong></span>: An intrusive singly linked list.
          The size overhead is very small for user classes (usually the size of one
          pointer) but many operations have linear time complexity, so the user must
          be careful if he wants to avoid performance problems.
        </li>
<li class="listitem">
          <span class="bold"><strong>list</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">list</span></code>
          like intrusive linked list. The size overhead is quite small for user classes
          (usually the size of two pointers). Many operations have constant time
          complexity.
        </li>
<li class="listitem">
          <span class="bold"><strong>set/multiset/rbtree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code>
          like intrusive associative containers based on red-black trees. The size
          overhead is moderate for user classes (usually the size of three pointers).
          Many operations have logarithmic time complexity.
        </li>
<li class="listitem">
          <span class="bold"><strong>avl_set/avl_multiset/avltree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
          based on AVL trees. The size overhead is moderate for user classes (usually
          the size of three pointers). Many operations have logarithmic time complexity.
        </li>
<li class="listitem">
          <span class="bold"><strong>splay_set/splay_multiset/splaytree</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
          based on splay trees. Splay trees have no constant operations, but they
          have some interesting caching properties. The size overhead is moderate
          for user classes (usually the size of three pointers). Many operations
          have logarithmic time complexity.
        </li>
<li class="listitem">
          <span class="bold"><strong>sg_set/sg_multiset/sgtree</strong></span>: A <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">multiset</span></code> like intrusive associative containers
          based on scapegoat trees. Scapegoat can be configured with the desired
          balance factor to achieve the desired rebalancing frequency/search time
          compromise. The size overhead is moderate for user classes (usually the
          size of three pointers). Many operations have logarithmic time complexity.
        </li>
</ul></div>
<p>
      <span class="bold"><strong>Boost.Intrusive</strong></span> also offers semi-intrusive
      containers:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "><li class="listitem">
          <span class="bold"><strong>unordered_set/unordered_multiset</strong></span>: <code class="computeroutput"><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_set</span><span class="special">/</span><span class="identifier">std</span><span class="special">::</span><span class="identifier">tr1</span><span class="special">::</span><span class="identifier">unordered_multiset</span></code> like intrusive unordered
          associative containers. The size overhead is moderate for user classes
          (an average of two pointers per element). Many operations have amortized
          constant time complexity.
        </li></ul></div>
<p>
      Most of these intrusive containers can be configured with constant or linear
      time size:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          <span class="bold"><strong>Linear time size</strong></span>: The intrusive container
          doesn't hold a size member that is updated with every insertion/erasure.
          This implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code> function doesn't have constant time complexity.
          On the other hand, the container is smaller, and some operations, like
          <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code>
          taking a range of iterators in linked lists, have constant time complexity
          instead of linear complexity.
        </li>
<li class="listitem">
          <span class="bold"><strong>Constant time size</strong></span>: The intrusive container
          holds a size member that is updated with every insertion/erasure. This
          implies that the <code class="computeroutput"><span class="identifier">size</span><span class="special">()</span></code>
          function has constant time complexity. On the other hand, increases the
          size of the container, and some operations, like <code class="computeroutput"><span class="identifier">splice</span><span class="special">()</span></code> taking a range of iterators, have linear
          time complexity in linked lists.
        </li>
</ul></div>
<p>
      To make user classes compatible with these intrusive containers <span class="bold"><strong>Boost.Intrusive</strong></span>
      offers two types of hooks for each container type:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          <span class="bold"><strong>Base hook</strong></span>: The hook is stored as a public
          base class of the user class.
        </li>
<li class="listitem">
          <span class="bold"><strong>Member hook</strong></span>: The hook is stored as a public
          member of the user class.
        </li>
</ul></div>
<p>
      Apart from that, <span class="bold"><strong>Boost.Intrusive</strong></span> offers additional
      features:
    </p>
<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; ">
<li class="listitem">
          <span class="bold"><strong>Safe mode hooks</strong></span>: Hook constructor initializes
          the internal <code class="computeroutput"><span class="identifier">node</span></code> to a
          well-known safe state and intrusive containers check that state before
          inserting a value in the container using that hook. When erasing an element
          from the container, the container puts the <code class="computeroutput"><span class="identifier">node</span></code>
          of the hook in the safe state again. This allows a safer use mode and it
          can be used to detect programming errors. It implies a slight performance
          overhead in some operations and can convert some constant time operations
          to linear time operations.
        </li>
<li class="listitem">
          <span class="bold"><strong>Auto-unlink hooks</strong></span>: The hook destructor
          removes the object from the container automatically and the user can safely
          unlink the object from the container without referring to the container.
        </li>
<li class="listitem">
          <span class="bold"><strong>Non-raw pointers</strong></span>: If the user wants to
          use smart pointers instead of raw pointers, <span class="bold"><strong>Boost.Intrusive</strong></span>
          hooks can be configured to use any type of pointer. This configuration
          information is also transmitted to the containers, so all the internal
          pointers used by intrusive containers configured with these hooks will
          be smart pointers. As an example, <span class="bold"><strong>Boost.Interprocess</strong></span>
          defines a smart pointer compatible with shared memory, called <code class="computeroutput"><span class="identifier">offset_ptr</span></code>. <span class="bold"><strong>Boost.Intrusive</strong></span>
          can be configured to use this smart pointer to allow shared memory intrusive
          containers.
        </li>
</ul></div>
</div>
<div class="copyright-footer">Copyright © 2005 Olaf Krzikalla<br>Copyright © 2006-2015 Ion Gaztanaga<p>
        Distributed under the Boost Software License, Version 1.0. (See accompanying
        file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>)
      </p>
</div>
<hr>
<div class="spirit-nav">
<a accesskey="p" href="concepts_summary.html"><img src="../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../intrusive.html"><img src="../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="safe_hook.html"><img src="../../../doc/src/images/next.png" alt="Next"></a>
</div>
</body>
</html>
